# 93/100 多维动态规划-最长会问子串
# leetcode第5题: https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/14
from leetcode.test import test_function as tf


def longestPalindrome(s: str) -> str:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    for left in range(n):
        for right in range(left, -1, -1):
            if left == right:
                dp[left][right] = True
            elif right == left - 1 and s[left] == s[right]:
                dp[left][right] = True
            else:
                dp[left][right] = (s[left] == s[right]) and (dp[left - 1][right + 1])
            if dp[left][right] and left - right + 1 > max_len:
                start = right
                max_len = left - right + 1
    return s[start: start + max_len]


if __name__ == '__main__':
    inp = [{"s": "babad"}, {"s": "cbbd"}, ]
    out = ["bab", "bb"]
    tf(longestPalindrome, inp, out)
